#include<bits/stdc++.h>
using namespace std;
const int N = 510;
const int P = 6;
int eg[N][N];
bool imp[N];
int n,m,p;
int fp[N];
bool has[N];
struct status{
    int val;
    bool chk(){
        vector<int> res(p);
        for(int i = 0;i < p;i++){
            res[i] = (val/fp[i])%(p + 1);

        }
        for(int i = 0;i < p;i++){
            if(res[i] == p){
                continue;
            }
            if(res[res[i]] != res[i]){
                return false;
            }
            if(res[i] > i){
                return false;
            }
        }
        return true;
    }
    int rat(int x){
        return (val/fp[x])%(p + 1);
    }
    void sat(int x,int v){
        if(x >= p)return;
        val -= rat(x)*fp[x];
        val += v*fp[x];
    }
};
void debug(unordered_map<int,long long> &mp){
    
}
void solve(){
    memset(eg,0x3f,sizeof(eg));
    cin>>n>>m>>p;
    for(int i = 1;i<=n;i++){
        char c;
        cin>>c;
        c -= '0';
        imp[i] = c;
    }
    has[n + 1] = 0;
    for(int i = n;i >= 1;i--){
        has[i] = has[i + 1] | imp[i];
    }
    for(int i = 1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        eg[u][v] = min(eg[u][v],w);
        eg[v][u] = min(eg[v][u],w);
    }
    // init
    fp[0] = 1;
    for(int i = 1;i <= p + 1;i++){
        fp[i] = fp[i - 1]*(p + 1);
    }
    unordered_map<int,long long> ss;
    for(int S = 0;S < fp[p];S++){
        status vl = {S};
        if(!vl.chk()){
            continue;
        }
        long long cost = 0;
        vector<vector<int>> rt(p + 1);
        for(int i = 0;i < p;i++){
            rt[vl.rat(i)].push_back(i);
        }
        bool f = 1;
        for(int v : rt[p]){
            if(imp[p - v]){
                f = 0;
                break;
            }
        }
        if(!f)continue;
        for(int i = 0;i < p;i++){
            if(rt[i].empty())continue;
            vector<int> fa(p);
            for(int i = 0;i < p;i++){
                fa[i] = i;
            }
            auto gf = [&fa](int x){
                while(fa[x] != x)x = fa[x];
                return x;
            };
            priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<tuple<int,int,int>>> que;
            for(int j = 0;j < rt[i].size();j++){
                for(int k = 0;k < j;k++){
                    int u = rt[i][j],v = rt[i][k],w = eg[p - u][p - v];
                    que.push(make_tuple(w,u,v));
                }
            }
            while(que.size()){
                int w,u,v;
                tie(w,u,v) = que.top();
                que.pop();
                int uu = gf(u),vv = gf(v);
                if(uu != vv){
                    fa[uu] = vv;
                    cost += w;
                }
            }
        }
        //if(cost > 6e6){
        //    continue;
        //}
        ss[S] = cost;
    }
    //debug(ss);
    long long ans = 0x3f3f3f3f3f3f3f3f;
    // dp
    for(int apos = p + 1;apos <= n;apos++){
        unordered_map<int,long long> ns;
        if(!imp[apos]){
            for(pair<int,long long> ost : ss){
                status vl = {ost.first};
                vector<vector<int>> rt(p + 1);
                for(int i = 0;i < p;i++){
                    rt[vl.rat(i)].push_back(i + 1);
                }
                if(rt[p - 1].size()){
                    if(rt[p - 1].size() + rt[p].size() == p && !has[apos]){
                        //cout<<ost.second<<'\n';
                        ans = min(ans,ost.second);
                    }
                    continue;
                }
                vector<vector<int>> nrt(p + 1);
                for(int i = 0;i < p - 1;i++){
                    nrt[i + 1] = rt[i];
                }
                nrt[p].push_back(0);
                for(int v : rt[p]){
                    nrt[p].push_back(v);
                }
                status nvl = {0};
                for(int i = 0;i <= p;i++){
                    for(int v: nrt[i]){
                        nvl.sat(v,i);
                    }
                }
                if(ns.find(nvl.val) == ns.end()){
                    ns[nvl.val] = 0x3f3f3f3f3f3f3f3f;
                }
                assert(nvl.chk());
                ns[nvl.val] = min(ns[nvl.val],ost.second);
            }
        }
        for(pair<int,long long> ost : ss){
            status vl = {ost.first};
            vector<vector<int>> rt(p + 1);
            for(int i = 0;i < p;i++){
                rt[vl.rat(i)].push_back(i + 1);
            }
            for(int S = 0;S < (1<<p);S++){
                vector<int> neb(1,0);
                vector<vector<int>> nrt = rt;
                long long cost = ost.second;
                bool f = 1;
                for(int i = 0;i < p;i++){
                    if((S>>i)&1){
                        cost += eg[apos][apos - i - 1];
                        //assert(eg[apos][apos - i - 1] == eg[apos - i - 1][apos]);
                        if(!nrt[vl.rat(i)].size()){ // has connect
                            f = 0;
                            break;
                        }
                        for(int v: nrt[vl.rat(i)]){
                            neb.push_back(v);
                        }
                        nrt[vl.rat(i)].clear();
                    }
                }
                if(!f){
                    continue;
                }
                if(nrt[p - 1].size()){
                    continue;
                }
                for(int i = p - 2;i >= 0;i--){
                    nrt[i + 1] = nrt[i];
                }
                nrt[0] = neb;
                status nvl = {0};
                for(int i = 0;i <= p;i++){
                    for(int v: nrt[i]){
                        nvl.sat(v,i);
                    }
                }
                if(ns.find(nvl.val) == ns.end()){
                    ns[nvl.val] = 0x3f3f3f3f3f3f3f3f;
                }
                assert(nvl.chk());
                ns[nvl.val] = min(ns[nvl.val],cost);
            }
        }
        ns.swap(ss);
        if(apos >= 15){
            //cerr<<apos<<'\n';
            debug(ss);
        }
    }
    for(pair<int,long long> st: ss){
        status vl = {st.first};
        vector<int> rtc(p + 1);
        for(int i = 0;i < p;i++){
            rtc[vl.rat(i)]++;
        }
        bool f = 1;
        for(int i = 0;i < p;i++){
            if(rtc[i] != 0 && rtc[i] != p - rtc[p]){
                f = 0;
                break;
            }
        }
        if(f){
            ans = min(ans,st.second);
        }
    }
    cout<<ans<<'\n';
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    freopen("connection.in","r",stdin);
    freopen("connection.out","w",stdout);
    int T;
    cin>>T;
    while(T--){
        solve();
    }
}